package day1_array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: yuisama
 * @Date: 2021/8/19 21:09
 * @Description:杨辉三角-给定非负行数，输出杨辉三角
 * 给定一个非负整数numRows，生成「杨辉三角」的前numRows行。
 *
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 * 示例 1:
 *
 * 输入: numRows = 5
 * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

 * 示例2:
 * 输入: numRows = 1
 * 输出: [[1]]
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pascals-triangle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Num118_PascalsTriangle {
    // 关键点在于子循环中get方法索引从0开始，而行数从1开始
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> listOne = Arrays.asList(1);
        List<Integer> listTwo = Arrays.asList(1,1);
        if (numRows == 1) {
            resultList.add(listOne);
        }
        else if (numRows == 2) {
            resultList.add(listOne);
            resultList.add(listTwo);
        }else {
            // 先把前两行装进结果集
            resultList.add(listOne);
            resultList.add(listTwo);
            // 取出结果集前一行的元素
            List<Integer> beforeList = resultList.get(1);
            for (int i = 3; i <= numRows; i++) {
                List<Integer> thisList = new ArrayList<>(i);
                thisList.add(1);
                // 循环i-2次存入相应位置元素
                for (int j = 1; j < i - 1; j++) {
                    thisList.add(beforeList.get(j) + beforeList.get(j - 1));
                }
                thisList.add(1);
                resultList.add(thisList);
                beforeList = thisList;
            }
        }
        return resultList;
    }
}
